package com.cuz.hot100;

import java.util.Stack;

public class Q32longestValidParentheses {

    public static void main(String[] args) {
        System.out.println(longestValidParentheses2("()(()"));
    }

    public static int longestValidParentheses1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int maxLen = 0;
        char[] chars = s.toCharArray();
        int[] dp = new int[chars.length];
        for (int index = 1; index < chars.length; index++) {
            if (chars[index] == ')') {
                //  ....()
                //1  () index=1 ==>0
                //2 ()() index=3  dp[3-2]=2 ==> dp[3]=2+2
                if (chars[index - 1] == '(') {
                    if (index - 2 >= 0) {
                        dp[index] = dp[index - 2] + 2;
                    } else {
                        dp[index] = 2;
                    }
                } else {
                    // (())   )()) index=3 dp[3-1]=2
                    //chars[0]=(  ===> 4 chars[0]=)==>0
                    //0->index-dp[index-1]-1
                    int preIndex = index - dp[index - 1] - 1;
                    if (preIndex >= 0) {

                        if (chars[preIndex] == '(') {
                            //  ?(())
                            dp[index] = dp[index - 1] + 2;
                            //如果 ？ 是 合法的还需要加上？的dp 如()(())
                            if (preIndex - 1 > 0) {
                                dp[index] += dp[preIndex - 1];
                            }
                        }
                    }
                }
            }
            maxLen = Math.max(maxLen, dp[index]);
        }
        return maxLen;
    }

    public static int longestValidParentheses2(String s) {
            int left = 0, right = 0, maxlength = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    left++;
                } else {
                    right++;
                }
                if (left == right) {
                    maxlength = Math.max(maxlength, 2 * right);
                } else if (right > left) {
                    left = right = 0;
                }
            }
            left = right = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
                if (s.charAt(i) == '(') {
                    left++;
                } else {
                    right++;
                }
                if (left == right) {
                    maxlength = Math.max(maxlength, 2 * left);
                } else if (left > right) {
                    left = right = 0;
                }
            }
            return maxlength;
        }

}
